/*
 * NetworkMaxFlow.java
 *
 * Created on 31 de enero de 2007, 11:09 AM
 */

package networkFlow;

/**
 *
 * @author tavobula
 */
public class NetworkMaxFlow {
    
    private Network G;
    private int s,t;
    private int[] wt;
    private Edge[] st;
    
    private int ST(int v){
        return st[v].other(v);
    }
    
    private void augment(int s, int t){
        int d=st[t].capRto(t);
        for(int v=ST(t); v!=s; v=ST(v))
            if(st[v].capRto(v)<d)
                d=st[v].capRto(v);
        st[t].addflowRto(t,d);
        for(int v=ST(t);v!=s;v=ST(v))
            st[v].addflowRto(v,d);
    } 
    
    private boolean pfs(){
        intPQi pQ=new intPQi(G.getV(), wt);
        for(int v=0; v<G.getV();++v){
            wt[v]=0; st[v]=null; pQ.insert(v);
        }
        wt[s]=-Edge.M;
        pQ.lower(s);
        while(!pQ.empty()){
            int v=pQ.getmin();
            wt[v]=-Edge.M;
            if(v==t)break;
            if(v!=s && st[v]==null)break;
            AdjList A = G.getAdjList(v);
            for(Edge e=A.beg();!A.end(); e=A.nxt()){
                int w=e.other(v);
                int cap=e.capRto(w);
                int P=cap < -wt[v]?cap:-wt[v];
                if(cap > 0 && -P < wt[w]){
                    wt[w]=-P; pQ.lower(w); st[w]=e;
                }
            }
        }
        return st[t]!=null;
            
        }
    
    
    /** Creates a new instance of NetworkMaxFlow */
    public NetworkMaxFlow(Network G, int s, int t) {
        this.G=G;
        this.s=s;
        this.t=t;
        wt=new int[G.getV()];
        st=new Edge[G.getV()];
        while (pfs()) augment(s,t);
    }

    
}
